package 回溯;
import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;
/*
 * 通过这个题的 dp 的解法  我好像明白了 动态规划的 本质了
 * 
 * 
 * 下标去重的 原理 好像是明白了 动手  画图分析出真知
 * 
 * 
 * 重新定义一下 这个 问题  
 * 1.数组中的 元素 是否 重复
 * 2.数组中的元素 是否 能够重复选取
 * 3. 是 返回 结果的集合 还是 返回形成这样要求的 集合 的 个数
 * 4.能 记忆化搜索 或者 dp的 是那些情况 
 * 直接总结 一下
 * 1.记忆化搜索的优化 和dp的优化 什么样的可以这样 优化
 * 2.去重的方法的 本质理解
 */
public class leetcode39组合一和二 {
	/*
	 * 递归 函数的 参数的选择 以及调整  
	 * 1.sum  和target 
	 * 2.直接一个 rest
	 *  下面的是组合 Ⅰ(一)leetcode39
	 *  容器中不存在重复元素 每个元素 可以重复 选取 
	 *  这样的 话  结果集 与结果集之间 是不会重复 的 重复的可能是 每个结果集自身 中的元素
	 *  没有去重的 意义
	 *  如果要求 结果集 自身的元素 不能重复的话 那样的 就是树枝去重 
	 */
	public static void main(String []args) {
//		int nums[]= {2,3,5};
//		System.out.println(process(nums,0,8));
//		System.out.println(solution(nums,8));
//		System.out.println(dp(nums,8));
		int candidates[] = {10,1,2,7,6,1,5};
		Arrays.sort(candidates);
		System.out.println(process1(candidates,0,8,candidates.length));
		System.out.println(solution(candidates,8));
	}
	//1. 返回 结果集合
	public static void process(int nums[],int index,int rest,LinkedList<Integer>path
			,List<List<Integer>> ans) {
		if(rest == 0) {
			ans.add(new ArrayList<>(path));
			return ;
		}
		// 剪枝 一般都是在 for循环中进行
		for(int i = index;i < nums.length &&rest -nums[i]>=0 ;i++) {
//			if(rest-nums[i]<0) {  加速 剪枝的速度
//				break;
//				
//			}
			path.add(nums[i]);
			process(nums,i,rest-nums[i],path,ans);
			path.removeLast();
		}
	} 
	//2.返回 结果的数目
	public static int process(int nums[],int index,int rest) {
		if(rest == 0) {
			return 1;
		}
		int ways=0;
		for(int i = index; i<nums.length && rest-nums[i]>=0; i++) {
			ways+=process(nums,i,rest-nums[i]);
		}
		return ways;
	}
	/*
	 *  记忆化搜索
	 * 首先 这个缓存表的 大小 以及 缓存表的值 表示的是什么意义
	 * 1.缓存表 根据  递归中 的 参数 列表中那些 是变化  就根据 这些变化的参数 来设计 这个缓存表
	 * 2.缓存表的值的意义 :  想一下 目的是什么    结果的数目
	 * 递归中只有两个参数 是变化的  所以这是 一个  二维表 而表中值的意义 就是你递归函数的目的的意义 到达 index位置 剩余rest
	 * 时候  的结果的数目   
	 */
	
	public static int solution(int nums[],int rest) {
		int len=nums.length;
		int dp[][] =new int[len][rest+1];
		// 对这个 二维表 进行初始化  画图分析一下 整个 缓存表的 是怎样计算 其实递归就是
		// 对应着 整个 缓存表的 状态转移的 过程 以及方向
		for(int j=0;j <= rest;j++) {
		for(int i=0;i < len;i++) {
				if(j==0) {
					dp[i][j]=1;
				}
				else {
					dp[i][j]=-1;
				}
			}
		}
		return process(nums,rest,0,dp,len);
//		return dp[0][rest];   这他妈 也可以省掉的 真正的 理解递归 这样不是手到擒来嘛
	}
	public static int process(int nums[],int rest,int index,int dp[][],int len) {
			if(dp[index][rest] !=-1) {
				return dp[index][rest];
			}
			int ways=0;
			for(int i=index;i < len && rest-nums[i]>=0;i++) {
				if(i > index && nums[i]==nums[i-1]) {
					continue;
				}
				//      39 与40 这两题的 优化 区别就在这里的 参数 不是i 而是i+1
				ways+=process(nums,rest-nums[i],i+1,dp,len);
			}
//			dp[index][rest]=ways;  这是 可以 省掉的  但是 这个ways 变量好像 省 不掉
			return dp[index][rest] = ways;
	}
	public static int dp(int nums[],int rest) {
		int len=nums.length;
		int dp[][] =new int[len][rest+1];
		for(int i=0;i < len;i++) {
			dp[i][0]=1;
		}
		// 下面是 对这个 二维缓存表 进行 转台转移的填值 
		// 这个 过程是根据 这个 二维表的填写  顺序来填  其实这个填写顺序 还可以 根据递归
		//看出来的
		for(int i= 1;i <=rest;i++) {
			for(int j=len-1;j>=0;j--) {
				int ways=0;
//下面这里 还可以继续优化嘛？？ 
				for(int k=j;k<len && i-nums[k]>=0;k++) {
					ways+=dp[k][i-nums[k]];
				}
				dp[j][i]=ways;//  填表时 这个位置 以及 索引值 不要搞混了
			}
		}
		return dp[0][rest];
	}
	/*
	 * 组合二 leetocde40；
	 * 容器中的元素 存在重复的 元素   且 每个元素不能重复选取
	 * 树层 去重 
	 * 去重的 方式： 1.used 数组  2. 直接根据 index   （两种方法的前提都是排序）  
	 */
	// 有没有这一种 可能  限制 结果集的 数目个数 为 k 
	public static void process1(int nums[],int index,int rest,LinkedList<Integer>path,
			List<List<Integer>> ans,int len) {
		if(rest==0) {
			ans.add(new ArrayList<>(path));
			return ;
		}
		//                        剪枝
		for(int i=index;i< len && rest-nums[i]>=0;i++) {
			// 注意 将 nums 集合排序
			if(i > index && nums[i]==nums[i-1]) {
				continue;
			}
			path.add(nums[i]);
			//      下面这一步 总是有时候 老是写 index+1 的错误写法
			process1(nums,i+1,rest-nums[i],path,ans,len);
			path.removeLast();
		}
	}
	//返回 形成要求的 结果集的个数
	public static int process1(int nums[],int index,int rest,int len) {
		if(rest==0) {
			return 1;
		}
		int ways=0;
		for(int i=index;i <len && rest-nums[i]>=0;i++ ) {
			if(i>index && nums[i]==nums[i-1]) {
				continue;
			}
			ways+=process1(nums,i+1,rest-nums[i],len);
		}
		return ways;
	}
	// 记忆化搜索 方法      除了 传递的参数哪里不一样 其他完全 跟 上面一样 这个 记忆化搜索 以及dp
//	public static int solution1(int nums[],int rest) {
//		int len=nums.length;
//		int dp[][]=new int[len][rest+1];
//		
//	}
}
